วันอังคารที่ 20 มกราคม พ.ศ. 2558
ทำความรู้จักกับ Mode ต่างๆของ Access Point กันดีกว่า
การใช้งานเครือข่ายไร้สายนั้น นอกจากเราจะใช้มันเป็นตัวเชื่อมต่อเข้ากับเครือข่ายหลักแบบมีสาย หรือที่เราเรียกว่า Infrastructure Mode หรือการทำงานที่ Access Point ธรรมดาๆทั่วไปทำงานได้เป็นพื้นฐานอยู่แล้ว
โหมด Access Point คือโหมดพื้นฐานที่สุดของการใช้งาน Wireless อยู่แล้วนั่นคือ Access Point จะทำหน้าที่ในการเชื่อมต่อเครื่องลูกข่ายเข้าสู่ ระบบเครือข่ายแบบมีสาย เพื่อเข้าไปใช้งานอินเตอร์เน็ต หรือเข้าไปยังเครือข่าย LAN ของสำนักงานเป็นต้น โดยการเข้าถึงเครือข่ายอาจจะมีการเข้ารหัส (Encryption) โดยผู้ใช้งานจะต้องใส่ Key ก่อนเชื่อมต่อ บนมาตรฐาน WEP หรือ WPA เป็นต้น
Client Router จะมีการทำงานคล้ายกับ Mode Client Bridge แต่ว่า Mode นี้อุปกรณ์จะทำหน้าที่ NAT (Network Address Translation) ด้วย และมีฟังก์ชั่น DHCP ที่สามารถแจก IP Addresss ให้กับเครื่องลูกด้วย ในโหมดนี้ จะใช้ Wireless เป็น interface WAN และ ใช้พอร์ต RJ-45 เป็น interface LAN
WDS AP ก็คือการทำ Repeater หรือการขยายสัญญาณ จาก AP ตัวหนึ่ง ไปยัง AP อีกตัวหนึ่ง (หรือหลายตัว) โดยสามารถทำการขยายต่อไปได้เรื่อยๆ (ยิ่งทำ WDS หลาย AP ความเร็วโดยรวมยิ่งตกลง) โดย WDS จะมีข้อดีกว่า Repeater คือ มันสามารถ ส่งผ่าน MAC Address ของ Client ผ่านไปยัง Interface Wireless ซึ่งเหมาะสำหรับ WISP ที่จะทำการ Repeat สัญญาณ
Universal Repeater นั้นอุปกรณ์จะทำหน้าที่ทวนสัญญาณจาก AP ตัวใดๆก็ได้ ที่อยู่ในรัศมี ที่อุปกรณ์รับสัญญาณได้ เพื่อขยายพื้นที่ให้บริการ รวมไปถึงมันยังสามารถเปลี่ยนชื่อ SSID เดิมให้เป็น SSID ใหม่ ที่เรากำหนดขึ้นได้ โหมดนี้ ถือเป็นโหมดเจ้าเล่ห์ ที่หาตัวจับยากจริงๆ
Bridge (บริดจ์) คือ อะไร
บริดจ์ เป็นอุปกรณ์เชื่อมโยงเครือข่ายของเครือข่ายที่แยกจากกัน แต่เดิมบริดจ์ได้รับการออกแบบมาให้ใช้กับเครือข่ายประเภทเดียวกัน เช่น ใช้เชื่อมโยงระหว่างอีเทอร์เน็ตกับ อีเทอร์เน็ต (Ethernet) บริดจ์มีใช้มานานแล้ว ตั้งแต่ปี ค.ศ.1980บริดจ์จึงเป็นเสมือนสะพานเชื่อมระหว่างสองเครือข่ายการติดต่อภายใน เครือข่ายเดียวกันมีลักษณะการส่ง ข้อมูลแบบกระจาย(Broadcasting)ดังนั้นจึงกระจายได้เฉพาะเครือข่ายเดียวกัน เท่านั้นการรับส่งภายในเครือข่ายมีข้อกำหนดให้แพ็กเก็ตที่ส่งกระจายไปยังตัว รับได้ทุกตัว แต่ถ้ามีการส่งมาที่แอดเดรสต่างเครือข่ายบริดจ์จะนำข้อมูลเฉพาะแพ็กเก็ตนั้น ส่งให้บริดจ์จึงเป็นเสมือนตัวแบ่งแยกข้อมูลระหว่างเครือข่ายให้มีการสื่อสาร ภายในเครือข่าย ของตน ไม่ปะปนไปยังอีกเครือข่ายหนึ่ง เพื่อลดปัญหาปริมาณข้อมูลกระจายในสายสื่อสารมากเกินไป ในระยะหลังมีผู้พัฒนาบริดจ์ให้เชื่อมโยงเครือข่ายต่างชนิดกันได้ เช่น อีเทอร์เน็ตกับโทเก็นริง เป็นต้น หากมีการเชื่อมต่อเครือข่ายมากกว่าสองเครือข่ายเข้าด้วยกัน และเครือข่ายที่เชื่อมมีลักษณะหลากหลาย ซึ่งเป็นทั้งเครือข่ายแบบ LAN และ WAN อุปกรณ์ที่นิยมใช้ในการเชื่อมโยงคือ เราเตอร์ (Router)
บริดจ์ เป็นอุปกรณ์ที่มักจะใช้ในการเชื่อมต่อวงแลน (LAN Segments)เข้าด้วยกันทำให้สามารถขยายขอบเขตของ LANออกไปได้เรื่อยๆโดยที่ประสิทธิภาพรวมของระบบไม่ลดลงมากนักเนื่องจากการ ติดต่อของเครื่องที่อยู่ในเซกเมนต์เดียวกันจะไม่ถูกส่งผ่านไปรบกวนการจราจร ของเซกเมนต์อื่น และเนื่องจากบริดจ์เป็นอุปกรณ์ที่ทำงานอยู่ในระดับ Data Link Layerจึงทำให้สามารถใช้ในการเชื่อมต่อเครือข่ายที่แตกต่างกันในระดับ Physical และ Data Link ได้ เช่น ระหว่าง Eternet กับ Token Ring เป็นต้น
Bridge
อุปกรณ์ Bridge เป็นสิ่งที่ใช้แก้ไขปัญหาในเรื่องสัญญาณที่วิ่งอยู่ในเครือข่ายมากเกินไปได้ โดยจะจัดแบ่งเครือข่ายออกเป็นเครือข่ายย่อยหรือ Network Segment และจะทำการกลั่นกรองสัญญาณเท่าที่จำเป็นเพื่อส่งให้กับเครือข่ายย่อยที่ถูก ต้องได้ ทำให้สัญญาณไม่มารบกวนกันหรือมีสัญญาณที่ไม่เกี่ยวข้องมาในเครือข่ายย่อย โดยไม่จำเป็น แต่ในทางกลับกัน ถ้ามีความจำเป็นต้องการสื่อสารกันข้ามเครือข่ายเป็นจำนวนมากแล้ว อุปกรณ์ Bridge ก็อาจกลายเป็นเสมือนคอขวดที่ทำให้เครือ่ข่าย มีการทำงานช้าลงได้
การทำงานของ Bridge
หลักการทำงานของ Bridge จะดูแลข้อมูลที่ส่งโดยพิจารณาหมายเลขของเครื่อง หรือตามศัพท์ทางเครือข่าย คือ Media Access Control (MAC Address หรือ Station Address) Bridge จะทำงานใน Data Link Layer หรือ Layer ที่ 2 ของ OSI โมเดล คือ มองข้อมูลที่รับส่งกัน เป็น Packet แล้วเท่านั้น โดยไม่ต้องสนใจโปรโตคอลสื่อสารที่ใช้ ไม่ว่าจะเป็น IP หรือ IPX หรือโปรโตคอลใด ๆ หรือก็คือ ไม่ว่าจะเป็น Packet อะไรส่งออกมาในเครือข่าย Bridge จะดูเฉพาะ Address ปลายทางแล้วถ้าพบว่าเป็นเครื่องที่อยู่คนละฟากกันก็จะส่งต่อให้เท่านั้น ไม่สนใจว่าการส่งให้ถึงเครื่อง ที่เป็นผู้รับปลายทางนั้นอาจทำได้หลายเส้นทางต่าง ๆ กัน
ข้อจำกัดอีกประการหนึ่งของ Bridge คือในขณะที่คอมพิวเตอร์เครื่องหนึ่งต้องการส่งข้อมูลไปยังอีกเครื่องหนึ่ง แต่ไม่ทราบ Station Address จะมีการส่งข้อมูล พิเศษที่เรียกว่า Broadcast Frame เข้าไปในเครือข่าย เมื่อข้อมูลนั้นผ่านมาที่ Bridge ก็จะมีการส่งข้อมูล Broadcast นี้ต่อไปยังทุกเครือข่ายย่อยทั้งหมดที่ ตนอยู่ โดยไม่มีการเลือกหรือกลั่นกรองใด ๆ ทำให้เครื่องคอมพิวเตอร์ในเครือข่ายทั้งหมดถูกขัดจังหวะเพื่อรับข้อมูลดัง กล่าว ดังนั้นถ้าข้อมูลที่ Broadcast มากก็จะ ทำให้เครือข่ายมีปัญหาเรื่องปริมาณข้อมูลหนาแน่น และความเร็วในการทำงานลดลงได้
อุปกรณ์ Bridge เป็นสิ่งที่ใช้แก้ไขปัญหาในเรื่องสัญญาณที่วิ่งอยู่ในเครือข่ายมากเกินไปได้ โดยจะจัดแบ่งเครือข่ายออกเป็นเครือข่ายย่อยหรือ Network Segment และจะทำการกลั่นกรองสัญญาณเท่าที่จำเป็นเพื่อส่งให้กับเครือข่ายย่อยที่ถูก ต้องได้ ทำให้สัญญาณไม่มารบกวนกันหรือมีสัญญาณที่ไม่เกี่ยวข้องมาในเครือข่ายย่อย โดยไม่จำเป็น แต่ในทางกลับกัน ถ้ามีความจำเป็นต้องการสื่อสารกันข้ามเครือข่ายเป็นจำนวนมากแล้ว อุปกรณ์ Bridge ก็อาจกลายเป็นเสมือนคอขวดที่ทำให้เครือ่ข่าย มีการทำงานช้าลงได้
การทำงานของ Bridge
หลักการทำงานของ Bridge จะดูแลข้อมูลที่ส่งโดยพิจารณาหมายเลขของเครื่อง หรือตามศัพท์ทางเครือข่าย คือ Media Access Control (MAC Address หรือ Station Address) Bridge จะทำงานใน Data Link Layer หรือ Layer ที่ 2 ของ OSI โมเดล คือ มองข้อมูลที่รับส่งกัน เป็น Packet แล้วเท่านั้น โดยไม่ต้องสนใจโปรโตคอลสื่อสารที่ใช้ ไม่ว่าจะเป็น IP หรือ IPX หรือโปรโตคอลใด ๆ หรือก็คือ ไม่ว่าจะเป็น Packet อะไรส่งออกมาในเครือข่าย Bridge จะดูเฉพาะ Address ปลายทางแล้วถ้าพบว่าเป็นเครื่องที่อยู่คนละฟากกันก็จะส่งต่อให้เท่านั้น ไม่สนใจว่าการส่งให้ถึงเครื่อง ที่เป็นผู้รับปลายทางนั้นอาจทำได้หลายเส้นทางต่าง ๆ กัน
ข้อจำกัดอีกประการหนึ่งของ Bridge คือในขณะที่คอมพิวเตอร์เครื่องหนึ่งต้องการส่งข้อมูลไปยังอีกเครื่องหนึ่ง แต่ไม่ทราบ Station Address จะมีการส่งข้อมูล พิเศษที่เรียกว่า Broadcast Frame เข้าไปในเครือข่าย เมื่อข้อมูลนั้นผ่านมาที่ Bridge ก็จะมีการส่งข้อมูล Broadcast นี้ต่อไปยังทุกเครือข่ายย่อยทั้งหมดที่ ตนอยู่ โดยไม่มีการเลือกหรือกลั่นกรองใด ๆ ทำให้เครื่องคอมพิวเตอร์ในเครือข่ายทั้งหมดถูกขัดจังหวะเพื่อรับข้อมูลดัง กล่าว ดังนั้นถ้าข้อมูลที่ Broadcast มากก็จะ ทำให้เครือข่ายมีปัญหาเรื่องปริมาณข้อมูลหนาแน่น และความเร็วในการทำงานลดลงได้
NAT คืออะไร
NAT สามารถแปลง IP หลายๆ ตัวที่ใช้ภายในเครือข่ายให้ติดต่อกับเครือข่ายอื่นโดยใช้ IP เดียวกัน ดู รูปข้างล่างครับ
จากภาพจะเห็นว่าตัว NAT device มี IP address เป็น 192.168.1.1 สำหรับเครือข่ายภายใน (inside network) และมี IP address เป็น 203.154.207.76 สำหรับเครือข่ายภายนอก (outside network) เมื่อเครื่อง 192.168.1.20 ต้องการ Export ทาง Internet NAT device ก็จะแปลง IP จาก 192.168.1.20 ไปเป็น 203.154.207.76 และข้อมูลขาออกที่ออกไปยัง external network นั้นจะเป็นข้อมูลที่มี source IP address เป็น outside IP address ของ NAT device
NAT มีขั้นตอนการทำงานอย่างไร
เมื่อ NAT เริ่มทำงาน มันจะสร้างตารางภายในซึ่งมีไว้สำหรับบรรจุข้อมูล IP address ของเครื่องในเครือข่ายภายในที่ส่ง packet ผ่าน NAT device และจากนั้นมันก็จะสร้างตารางไว้สำหรับเก็บข้อมูลหมายเลขพอร์ต (port number) ที่ถูกใช้ไปโดย outside IP address จะมีกระบวนการทำงานดังนี้
1.มัน จะบันทึกข้อมูล source IP adress และ source port number ไว้ใน Log File
2.มัน จะแทนที่ IP ของ packet ด้วย IP ขาออกของ NAT device เอง
และเมื่อ NAT device ได้รับ packet ย้อนกลับมาจาก external network มันจะตรวจสอบ destination port number ของ packet นั้นๆ แล้วนำมาเปรียบเทียบกับข้อมูล source port number ใน Log File ถ้าเจอข้อมูลที่ตรงกันมันก็จะเขียนทับ destination port number, destination IP address ของ pakcet นั้นๆ แล้วจึงส่ง packet นั้นไปยังเครื่องอยู่ภายในเครือข่ายภายใน
ข้อ ดีของ Outbound Mode NAT เมื่อเปรียบเทียบกับ Firewall
NAT ทำงานได้ในระดับเดียวกันกับไฟร์วอลล์และไม่ต้องการความรู้ด้านเทคนิคมากมาย นัก NAT สามารถซ่อน internal network IP address จากเครือข่ายภายนอกไว้ได้ ซึ่งผู้ที่อยู่ภายนอกจะมองเห็นแค่เพียง outside IP address ของ NAT device เท่านั้น ดังนั้นโอกาสในการ broadcast หรือ hack หรือ spoof จึงแทบไม่มีโอกาสเป็นไปได้
ความง่ายในการดูแลเครือข่ายที่ใช้ NAT
1.เนื่อง จากเราสามารถใช้ non-routable address ในเครือข่ายภายใน ซึ่งสามารถใช้ได้อย่างมากมาย จึงทำให้ลดค่าใช้จ่ายสำหรับ routable address ลงไปได้
NAT มีความปลอดภัยหรือไม่ ?
ถ้ามี NAT แล้วก็ไม่จำเป็นต้องมีไฟร์วอลล์ ซึ่งจริงๆแล้ว NAT ต้องเปิดพอร์ตให้บริการเสมอ เช่น 20-21 (FTP), 23(TELNET), 25 (SMTP), 53 (DNS), 80 (HTTP), 110 (POP), 143 (IMAP) นอกจากนี้การที่ user ใน internal network รันโปรแกรมบนเครื่องตัวเอง ซึ่งโปรแกรมนั้นอาจจะเป็นม้าโทรจันก็เป็นไปได้ จากนั้นม้าโทรจันก็จะส่ง packet ออกไป external network ซึ่ง NAT ก็จะปล่อยให้ packet ผ่านไปได้เพราะถือว่าเป็นการ request จาก internal side ในกรณีนี้ก็จะเห็นได้ว่า NAT ไม่ได้ช่วยอะไรได้เลย
ด้วย NAT นี่เองทำให้จาก external เข้ามาทำได้ยากขึ้น(เข้าจากพอร์ตไม่ปกติ--->port ที่ไม่ใช่ Well known Ports Number)
เช่น
เครื่อง ก อยู่ใน NAT แล้วเครื่อง ข จะทำมิดีมิร้าย เครื่อง ก
เครื่อง ข จะไม่สามารเข้าถึงเครื่อง ก ได้ เพราะติด NAT นั่นเอง เฮ้อ... เศร้า.....
ปล.แล้วจะทำไงดีน้อ....
ปล2.ผิด พลาดประการใดก็ขออภัยด้วยครับ...
สอบถามนิดนะครับคือว่าสงสัยนะครับ ว่าจริงๆแล้ว ถ้าเครื่องข้างนอกกเป็น public IP แล้วเครื่องข้างในเป็น Private IP เช่น ถ้าผมมี public IP ใช้งานอยู่เครื่องหนึ่งมันสามารถ ping ไปสู่เครื่องข้างในที่ป็น Private IP ได้หรือเปล่าว ถ้าเราตัดส่วนที่เป็น firewall ออกไป โดยไม่คำนึงถึง
จากรูปแล้วของคุณ Alternative นั้น เวลาเราทำ NAT นั้นเราจะให้ออกด้วย Public IP แต่ที่นี้เราจะให้ออกโดยเป็น interface ที่เราให้เป็น IP PUBLIC เลย ก็คือ 203.154.207.76 หรือเปล่าวครับ หรือว่า เราต้องหา IP PUBLIC อีกอันมา MAP ถ้าสมมติว่า ผมให้เครื่อง 192.168.1.20 นั้นออกด้วย IP PUBLIC ที่เป็น 203.154.207.76 ของ interface ใน device ที่ทำ NAT มันจะเรียกเป็นการทำ NAT แบบ 1:1 หรือว่า เป็นแบบ Dynamic NAT อ่ะครับ เพราะเท่าที่ผมรู้มาว่าถ้าทำแบบนี้เขาจะเรียกว่า Dynamic NAT เพราะเคยเห็นคนพูดกันว่าตามหลักจริงๆแล้ว ในการทำ NAT เราต้องหา IP PUBLIC อีกอันหนึ่งมาใช้ในการทำ NAT ต้องไม่ใช้ interface device ที่ทำ NAT ถึงแม้ว่าจะเป็น PUBLIC IP ไม่รู้ทั่วๆไปสากลเขาใช้แบบนี้ที่ผมกล่าวถึงหรือเปล่าวครับ รบกวนพี่ที่เก่งๆและแม่นในทฤษฏีหน่อยนะครับ ขอบคุณมากครับ
สงสัยคับ คือว่าหากเราทำ static NAT private 192.168.0.5 public 203.xxx.yyy.zzz ไว้ที่ router
เครื่องผมอีกคเครื่องหนึ่งอยู่ในวง private จะ remote เข้าเครื่อง 192.168.0.5 ถึงไม่สามารถใช้ IP public ได้ครับ
NAT จะมีอยู่ สามแบบครับ
แบบแรก NAT Static จะอาศัยโดยการ 1 private IP ต่อ หนึ่ง Public IP ครับ หนึ่งเครื่องต่อหนึ่งครับไม่สามารถสร้างได้มากครับ
แบบที่สอง NAT Dynamic จะหาศัยการเชื่อมต่อแบบ ไอพีการเปลี่ยนแปลงตลอดเวลา ครับ เช่นว่า host 20 และมี Public IP 10 ไอพี เช่นว่า Public IP ตั้งแต่ 183.89.160.1 - 183.89.160.10 และภาพใน 20 เครื่องนั้นมาก่อนจะได้ ไอพี Public IP จริงออกไป 183.89.160.1 และเครื่องต่อมาติดๆกัน มาอีก ไอพี183.89.160.1 ไม่ว่าง Routerจะจ่ายไอพีเครื่องที่สอง Public IP เป็น 183.89.160.2 ครับ ไปอย่างนี้เรื่อย และวนซ้ำกลับมาครับ จะสอบว่าไอพีไหนว่างก็เสียบเข้าเลย
แบบสาม NAT Overload แบบนี้วิธีการนี้มักจะมีอยู่ตามกันใช้ทั่วไป ADSL คือจะมี Public IP มี แค่ หนึ่ง ไอพีเท่านี้นและเครืองในองค์กรหรือในบ้าน ไม่เพียงพอ เราจำเป็นต้องสร้างไอพีภายในให้ คือ private ip เพราะว่าในโลกความเป็นไอพีไม่เพียงพอต่อคอมพิวเตอร์ จึงจำแปลงต้องมีการแปลง ไอพี ภายใน ให้เป็นไอพี public เพื่อที่จะได้ออกเล่นอินเตอร์เน็ตได้ โดยอาศัยพอร์ตการเชื่อมต่อเอา มาจากไอพีไหน เช่นว่า 192.168.10:2536 สังเกตจะมีพอมาเรื่อยๆในเครื่องเราขณะเล่นเน็ต ลอง start -> run -> cmd -> netstat -5 ดูครับ จะดูว่าจะมีการเชื่อมต่อทุกๆห้าวินาที มีใครมาเชื่อมต่อบ้างอาศัยพอร์ดไหน จะรู้ ปลายต้นและต้นทางที่เชื่อมครับ
ที่มา : http://thaicourt.blogspot.com/2010/12/nat.html
จากภาพจะเห็นว่าตัว NAT device มี IP address เป็น 192.168.1.1 สำหรับเครือข่ายภายใน (inside network) และมี IP address เป็น 203.154.207.76 สำหรับเครือข่ายภายนอก (outside network) เมื่อเครื่อง 192.168.1.20 ต้องการ Export ทาง Internet NAT device ก็จะแปลง IP จาก 192.168.1.20 ไปเป็น 203.154.207.76 และข้อมูลขาออกที่ออกไปยัง external network นั้นจะเป็นข้อมูลที่มี source IP address เป็น outside IP address ของ NAT device
NAT มีขั้นตอนการทำงานอย่างไร
เมื่อ NAT เริ่มทำงาน มันจะสร้างตารางภายในซึ่งมีไว้สำหรับบรรจุข้อมูล IP address ของเครื่องในเครือข่ายภายในที่ส่ง packet ผ่าน NAT device และจากนั้นมันก็จะสร้างตารางไว้สำหรับเก็บข้อมูลหมายเลขพอร์ต (port number) ที่ถูกใช้ไปโดย outside IP address จะมีกระบวนการทำงานดังนี้
1.มัน จะบันทึกข้อมูล source IP adress และ source port number ไว้ใน Log File
2.มัน จะแทนที่ IP ของ packet ด้วย IP ขาออกของ NAT device เอง
และเมื่อ NAT device ได้รับ packet ย้อนกลับมาจาก external network มันจะตรวจสอบ destination port number ของ packet นั้นๆ แล้วนำมาเปรียบเทียบกับข้อมูล source port number ใน Log File ถ้าเจอข้อมูลที่ตรงกันมันก็จะเขียนทับ destination port number, destination IP address ของ pakcet นั้นๆ แล้วจึงส่ง packet นั้นไปยังเครื่องอยู่ภายในเครือข่ายภายใน
ข้อ ดีของ Outbound Mode NAT เมื่อเปรียบเทียบกับ Firewall
NAT ทำงานได้ในระดับเดียวกันกับไฟร์วอลล์และไม่ต้องการความรู้ด้านเทคนิคมากมาย นัก NAT สามารถซ่อน internal network IP address จากเครือข่ายภายนอกไว้ได้ ซึ่งผู้ที่อยู่ภายนอกจะมองเห็นแค่เพียง outside IP address ของ NAT device เท่านั้น ดังนั้นโอกาสในการ broadcast หรือ hack หรือ spoof จึงแทบไม่มีโอกาสเป็นไปได้
ความง่ายในการดูแลเครือข่ายที่ใช้ NAT
1.เนื่อง จากเราสามารถใช้ non-routable address ในเครือข่ายภายใน ซึ่งสามารถใช้ได้อย่างมากมาย จึงทำให้ลดค่าใช้จ่ายสำหรับ routable address ลงไปได้
อ้างถึง
non-routable address คือ IP address ที่อยู่ในช่วงที่ถูกสำรองไว้ เช่น 10.x, 172.16.x - 172.31.x, 192.168.x หรือเรียกว่า private IP address
2.มี traffic logging คือมีการบันทึกข้อมูลลงล็อกไฟล์ ทำให้สามารถตรวจสอบรายงานการใช้งานได้ NAT มีความปลอดภัยหรือไม่ ?
ถ้ามี NAT แล้วก็ไม่จำเป็นต้องมีไฟร์วอลล์ ซึ่งจริงๆแล้ว NAT ต้องเปิดพอร์ตให้บริการเสมอ เช่น 20-21 (FTP), 23(TELNET), 25 (SMTP), 53 (DNS), 80 (HTTP), 110 (POP), 143 (IMAP) นอกจากนี้การที่ user ใน internal network รันโปรแกรมบนเครื่องตัวเอง ซึ่งโปรแกรมนั้นอาจจะเป็นม้าโทรจันก็เป็นไปได้ จากนั้นม้าโทรจันก็จะส่ง packet ออกไป external network ซึ่ง NAT ก็จะปล่อยให้ packet ผ่านไปได้เพราะถือว่าเป็นการ request จาก internal side ในกรณีนี้ก็จะเห็นได้ว่า NAT ไม่ได้ช่วยอะไรได้เลย
ด้วย NAT นี่เองทำให้จาก external เข้ามาทำได้ยากขึ้น(เข้าจากพอร์ตไม่ปกติ--->port ที่ไม่ใช่ Well known Ports Number)
เช่น
เครื่อง ก อยู่ใน NAT แล้วเครื่อง ข จะทำมิดีมิร้าย เครื่อง ก
เครื่อง ข จะไม่สามารเข้าถึงเครื่อง ก ได้ เพราะติด NAT นั่นเอง เฮ้อ... เศร้า.....
ปล.แล้วจะทำไงดีน้อ....
ปล2.ผิด พลาดประการใดก็ขออภัยด้วยครับ...
สอบถามนิดนะครับคือว่าสงสัยนะครับ ว่าจริงๆแล้ว ถ้าเครื่องข้างนอกกเป็น public IP แล้วเครื่องข้างในเป็น Private IP เช่น ถ้าผมมี public IP ใช้งานอยู่เครื่องหนึ่งมันสามารถ ping ไปสู่เครื่องข้างในที่ป็น Private IP ได้หรือเปล่าว ถ้าเราตัดส่วนที่เป็น firewall ออกไป โดยไม่คำนึงถึง
จากรูปแล้วของคุณ Alternative นั้น เวลาเราทำ NAT นั้นเราจะให้ออกด้วย Public IP แต่ที่นี้เราจะให้ออกโดยเป็น interface ที่เราให้เป็น IP PUBLIC เลย ก็คือ 203.154.207.76 หรือเปล่าวครับ หรือว่า เราต้องหา IP PUBLIC อีกอันมา MAP ถ้าสมมติว่า ผมให้เครื่อง 192.168.1.20 นั้นออกด้วย IP PUBLIC ที่เป็น 203.154.207.76 ของ interface ใน device ที่ทำ NAT มันจะเรียกเป็นการทำ NAT แบบ 1:1 หรือว่า เป็นแบบ Dynamic NAT อ่ะครับ เพราะเท่าที่ผมรู้มาว่าถ้าทำแบบนี้เขาจะเรียกว่า Dynamic NAT เพราะเคยเห็นคนพูดกันว่าตามหลักจริงๆแล้ว ในการทำ NAT เราต้องหา IP PUBLIC อีกอันหนึ่งมาใช้ในการทำ NAT ต้องไม่ใช้ interface device ที่ทำ NAT ถึงแม้ว่าจะเป็น PUBLIC IP ไม่รู้ทั่วๆไปสากลเขาใช้แบบนี้ที่ผมกล่าวถึงหรือเปล่าวครับ รบกวนพี่ที่เก่งๆและแม่นในทฤษฏีหน่อยนะครับ ขอบคุณมากครับ
สงสัยคับ คือว่าหากเราทำ static NAT private 192.168.0.5 public 203.xxx.yyy.zzz ไว้ที่ router
เครื่องผมอีกคเครื่องหนึ่งอยู่ในวง private จะ remote เข้าเครื่อง 192.168.0.5 ถึงไม่สามารถใช้ IP public ได้ครับ
NAT จะมีอยู่ สามแบบครับ
แบบแรก NAT Static จะอาศัยโดยการ 1 private IP ต่อ หนึ่ง Public IP ครับ หนึ่งเครื่องต่อหนึ่งครับไม่สามารถสร้างได้มากครับ
แบบที่สอง NAT Dynamic จะหาศัยการเชื่อมต่อแบบ ไอพีการเปลี่ยนแปลงตลอดเวลา ครับ เช่นว่า host 20 และมี Public IP 10 ไอพี เช่นว่า Public IP ตั้งแต่ 183.89.160.1 - 183.89.160.10 และภาพใน 20 เครื่องนั้นมาก่อนจะได้ ไอพี Public IP จริงออกไป 183.89.160.1 และเครื่องต่อมาติดๆกัน มาอีก ไอพี183.89.160.1 ไม่ว่าง Routerจะจ่ายไอพีเครื่องที่สอง Public IP เป็น 183.89.160.2 ครับ ไปอย่างนี้เรื่อย และวนซ้ำกลับมาครับ จะสอบว่าไอพีไหนว่างก็เสียบเข้าเลย
แบบสาม NAT Overload แบบนี้วิธีการนี้มักจะมีอยู่ตามกันใช้ทั่วไป ADSL คือจะมี Public IP มี แค่ หนึ่ง ไอพีเท่านี้นและเครืองในองค์กรหรือในบ้าน ไม่เพียงพอ เราจำเป็นต้องสร้างไอพีภายในให้ คือ private ip เพราะว่าในโลกความเป็นไอพีไม่เพียงพอต่อคอมพิวเตอร์ จึงจำแปลงต้องมีการแปลง ไอพี ภายใน ให้เป็นไอพี public เพื่อที่จะได้ออกเล่นอินเตอร์เน็ตได้ โดยอาศัยพอร์ตการเชื่อมต่อเอา มาจากไอพีไหน เช่นว่า 192.168.10:2536 สังเกตจะมีพอมาเรื่อยๆในเครื่องเราขณะเล่นเน็ต ลอง start -> run -> cmd -> netstat -5 ดูครับ จะดูว่าจะมีการเชื่อมต่อทุกๆห้าวินาที มีใครมาเชื่อมต่อบ้างอาศัยพอร์ดไหน จะรู้ ปลายต้นและต้นทางที่เชื่อมครับ
ที่มา : http://thaicourt.blogspot.com/2010/12/nat.html
วันจันทร์ที่ 19 มกราคม พ.ศ. 2558
วันอังคารที่ 13 มกราคม พ.ศ. 2558
วันจันทร์ที่ 12 มกราคม พ.ศ. 2558
เปิด Firefox ใน Ubuntu ขึ้นมา
ให้เราพิมพ์ about:config ลงใน URL address bar ของ firefox จากนั้นตั้งค่าตามนี้ แล้ว กด ที่ i"ll be careful,i promise!
จะได้ภาพ ตามด้านล่างนี้ แก้ตาม
แก้ไขตามด้านล่างนี้
network.http.pipelining > กำหนดเป็น True
network.http.pipelining.maxrequests > แก้ไขจาก 32 ไปเป็น 10
network.http.proxy.pipelining > กำหนดเป็น True
network.dns.disableIPv6 > กำหนดเป็น True
เท่านี้เราก็เล่นอินเตอร์ได้ตามปกติครับ แต่ยังไม่ เสถียรน๊ะคับ
By Arcsh
วันศุกร์ที่ 7 พฤศจิกายน พ.ศ. 2557
New way to make batteries safer
Coating prevents electrical current from damaging the digestive tract after battery ingestion.
Anne Trafton | MIT News Office November 3, 2014
Every year, nearly 4,000 children go to emergency rooms after swallowing button batteries — the flat, round batteries that power toys, hearing aids, calculators, and many other devices. Ingesting these batteries has severe consequences, including burns that permanently damage the esophagus, tears in the digestive tract, and in some cases, even death.
To help prevent such injuries, researchers at MIT, Brigham and Women’s Hospital, and Massachusetts General Hospital have devised a new way to coat batteries with a special material that prevents them from conducting electricity after being swallowed. In animal tests, they found that such batteries did not damage the gastrointestinal (GI) tract at all.
“We are all very pleased that our studies have shown that these new batteries we created have the potential to greatly improve safety due to accidental ingestion for the thousands of patients every year who inadvertently swallow electric components in toys or other entities,” says Robert Langer, the David H. Koch Institute Professor at MIT and a member of MIT’s Koch Institute for Integrative Cancer Research, Institute for Medical Engineering and Science (IMES), and Department of Chemical Engineering.
Langer and Jeffrey Karp, an associate professor of medicine at Harvard Medical School and Brigham and Women’s Hospital, are the senior authors of a paper describing the new battery coatings in this week’s edition of the Proceedings of the National Academy of Sciences. The paper’s lead authors are Bryan Laulicht, a former IMES postdoc, and Giovanni Traverso, a research fellow at the Koch Institute and a gastroenterologist at MGH.
Small batteries, big danger
About 5 billion button batteries are produced every year, and these batteries have become more and more powerful, making them even more dangerous if swallowed. In the United States, recent legislation has mandated warning labels on packages, and some toys are required to have battery housings that can only be opened with a screwdriver. However, there have been no technological innovations to make the batteries themselves safer, Karp says.
When batteries are swallowed, they start interacting with water or saliva, creating an electric current that produces hydroxide, a caustic ion that damages tissue. This can cause serious injury within just a couple of hours, especially if parents don’t realize right away that a child has swallowed a battery.
“Disc batteries in the esophagus require [emergency] endoscopic removal,” Traverso says. “This represents a gastrointestinal emergency, given that tissue damage starts as soon as the battery is in contact with the tissue, generating an electric current [and] leading to a chemical burn.”
The research team began thinking about ways to alter batteries so they would not generate a current inside the human body but would still be able to power a device. They knew that when batteries are inside their housing, they experience a gentle pressure. To take advantage of this, they decided to coat the batteries with a material that would allow them to conduct when under pressure, but would act as an insulator when the batteries are not being compressed.
Quantum tunneling composite (QTC), an off-the-shelf material commonly used in computer keyboards and touch screens, fit the bill perfectly. QTC is a rubberlike material, usually made of silicone, embedded with metal particles. Under normal circumstances, these particles are too far apart to conduct an electric current. However, when squeezed, the particles come closer together and start conducting. This allows QTC to switch from an insulator to a conductor, depending on how much pressure it is under.
To verify that this coating would protect against tissue damage, the researchers first calculated how much pressure the battery would experience inside the digestive tract, where movements of the tract, known as peristalsis, help move food along. They calculated that even under the highest possible forces, found in patients with a rare disorder called “nutcracker esophagus,” the QTC-coated batteries would not conduct.
“You want to know what’s the maximum force that could possibly be applied, and you want to make sure the batteries will conduct only above that threshold,” Laulicht says. “We felt that once we were well above those levels, these coatings would pass through the GI tract unchanged.”
After those calculations were done, the researchers monitored the coated batteries in the esophagus of a pig, and found no signs of damage.
“A relatively simple solution”
Because QTC is relatively inexpensive and already used in other consumer products, the researchers believe battery companies could implement this type of coating fairly easily. They are now working on developing a scalable method for manufacturing coated batteries and seeking companies that would be interesting in adopting them.
“We were really interested in trying to impose design criteria that would allow us to have an accelerated path to get this out into society and reduce injuries,” Karp says. “We think this is a relatively simple solution that should be easy to scale, won’t add significant cost, and can address one of the biggest problems associated with ingestion of these batteries.”
Also, because the coating is waterproof, the researchers believe it could be used to make batteries weather-resistant and more suitable for outdoor use. They also plan to test the coating on other types of batteries, including lithium batteries.
Edith Mathiowitz, a professor of medical science at Brown University who was not involved in the research, says she believes this approach is a “brilliant idea” that offers an easy fix for the potential dangers of battery ingestion.
“What I like about it is that it’s a simple idea you could implement very easily. It’s not something that requires a big new manufacturing facility,” she says. “And, it could be useful eventually in any type of size of battery.”
The research was funded by the National Institutes of Health.
To help prevent such injuries, researchers at MIT, Brigham and Women’s Hospital, and Massachusetts General Hospital have devised a new way to coat batteries with a special material that prevents them from conducting electricity after being swallowed. In animal tests, they found that such batteries did not damage the gastrointestinal (GI) tract at all.
“We are all very pleased that our studies have shown that these new batteries we created have the potential to greatly improve safety due to accidental ingestion for the thousands of patients every year who inadvertently swallow electric components in toys or other entities,” says Robert Langer, the David H. Koch Institute Professor at MIT and a member of MIT’s Koch Institute for Integrative Cancer Research, Institute for Medical Engineering and Science (IMES), and Department of Chemical Engineering.
Langer and Jeffrey Karp, an associate professor of medicine at Harvard Medical School and Brigham and Women’s Hospital, are the senior authors of a paper describing the new battery coatings in this week’s edition of the Proceedings of the National Academy of Sciences. The paper’s lead authors are Bryan Laulicht, a former IMES postdoc, and Giovanni Traverso, a research fellow at the Koch Institute and a gastroenterologist at MGH.
Small batteries, big danger
About 5 billion button batteries are produced every year, and these batteries have become more and more powerful, making them even more dangerous if swallowed. In the United States, recent legislation has mandated warning labels on packages, and some toys are required to have battery housings that can only be opened with a screwdriver. However, there have been no technological innovations to make the batteries themselves safer, Karp says.
When batteries are swallowed, they start interacting with water or saliva, creating an electric current that produces hydroxide, a caustic ion that damages tissue. This can cause serious injury within just a couple of hours, especially if parents don’t realize right away that a child has swallowed a battery.
“Disc batteries in the esophagus require [emergency] endoscopic removal,” Traverso says. “This represents a gastrointestinal emergency, given that tissue damage starts as soon as the battery is in contact with the tissue, generating an electric current [and] leading to a chemical burn.”
The research team began thinking about ways to alter batteries so they would not generate a current inside the human body but would still be able to power a device. They knew that when batteries are inside their housing, they experience a gentle pressure. To take advantage of this, they decided to coat the batteries with a material that would allow them to conduct when under pressure, but would act as an insulator when the batteries are not being compressed.
Quantum tunneling composite (QTC), an off-the-shelf material commonly used in computer keyboards and touch screens, fit the bill perfectly. QTC is a rubberlike material, usually made of silicone, embedded with metal particles. Under normal circumstances, these particles are too far apart to conduct an electric current. However, when squeezed, the particles come closer together and start conducting. This allows QTC to switch from an insulator to a conductor, depending on how much pressure it is under.
To verify that this coating would protect against tissue damage, the researchers first calculated how much pressure the battery would experience inside the digestive tract, where movements of the tract, known as peristalsis, help move food along. They calculated that even under the highest possible forces, found in patients with a rare disorder called “nutcracker esophagus,” the QTC-coated batteries would not conduct.
“You want to know what’s the maximum force that could possibly be applied, and you want to make sure the batteries will conduct only above that threshold,” Laulicht says. “We felt that once we were well above those levels, these coatings would pass through the GI tract unchanged.”
After those calculations were done, the researchers monitored the coated batteries in the esophagus of a pig, and found no signs of damage.
“A relatively simple solution”
Because QTC is relatively inexpensive and already used in other consumer products, the researchers believe battery companies could implement this type of coating fairly easily. They are now working on developing a scalable method for manufacturing coated batteries and seeking companies that would be interesting in adopting them.
“We were really interested in trying to impose design criteria that would allow us to have an accelerated path to get this out into society and reduce injuries,” Karp says. “We think this is a relatively simple solution that should be easy to scale, won’t add significant cost, and can address one of the biggest problems associated with ingestion of these batteries.”
Also, because the coating is waterproof, the researchers believe it could be used to make batteries weather-resistant and more suitable for outdoor use. They also plan to test the coating on other types of batteries, including lithium batteries.
Edith Mathiowitz, a professor of medical science at Brown University who was not involved in the research, says she believes this approach is a “brilliant idea” that offers an easy fix for the potential dangers of battery ingestion.
“What I like about it is that it’s a simple idea you could implement very easily. It’s not something that requires a big new manufacturing facility,” she says. “And, it could be useful eventually in any type of size of battery.”
The research was funded by the National Institutes of Health.
วันพฤหัสบดีที่ 6 พฤศจิกายน พ.ศ. 2557
Can you out-race a computer?
Can you out-race a computer?
Deep-learning algorithm can weigh up a neighborhood better than humans.
Human beings have a remarkable ability to make inferences based on their surroundings. Is this area safe? Where might I find a parking spot? Am I more likely to get to a gas station by taking a left or a right at this stoplight?
Such decisions require us to look beyond our “visual scene” and weigh an exceedingly complex set of understandings and real-time judgments. This begs the question: Can we teach computers to “see” in the same way? And once we teach them, can they do it better than we can?
The answers are “yes” and “sometimes,” according to research out of MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL). Researchers have developed an algorithm that can look at a pair of photos and outperform humans in determining things like which scene has a higher crime rate, or is closer to a McDonald's restaurant.
An online demo puts you in the middle of a Google Street View with four directional options and challenges you to navigate to the nearest McDonald's in the fewest possible steps.
While humans are generally better at this specific task than the algorithm, the researchers found that the computer consistently outperformed humans at a variation of the task in which users are shown two photos and asked which scene is closer to a McDonald's.
To create the algorithm, the team — which included PhD students Aditya Khosla, Byoungkwon An, and Joseph Lim, as well as CSAIL principal investigator Antonio Torralba — trained the computer on a set of 8 million Google images from eight major U.S. cities that were embedded with GPS data on crime rates and McDonald's locations. They then used deep-learning techniques to help the program teach itself how different qualities of the photos correlate. For example, the algorithm independently discovered that some things you often find near McDonald's franchises include taxis, police vans, and prisons. (Things you don’t find: cliffs, suspension bridges, and sandbars.)
“These sorts of algorithms have been applied to all sorts of content, like inferring the memorability of faces from headshots,” said Khosla. “But before this, there hadn’t really been research that’s taken such a large set of photos and used it to predict qualities of the specific locations the photos represent.”
The researchers presented a paper about the work at the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR) this summer.
While the project was mostly intended as proof that computer algorithms are capable of advanced scene understanding, Khosla has brainstormed potential uses ranging from a navigation app that avoids high-crime areas, to a tool that could help McDonald's determine future franchise locations.
Khosla previously helped develop an algorithm that can predict a photo’s popularity.
Such decisions require us to look beyond our “visual scene” and weigh an exceedingly complex set of understandings and real-time judgments. This begs the question: Can we teach computers to “see” in the same way? And once we teach them, can they do it better than we can?
The answers are “yes” and “sometimes,” according to research out of MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL). Researchers have developed an algorithm that can look at a pair of photos and outperform humans in determining things like which scene has a higher crime rate, or is closer to a McDonald's restaurant.
An online demo puts you in the middle of a Google Street View with four directional options and challenges you to navigate to the nearest McDonald's in the fewest possible steps.
While humans are generally better at this specific task than the algorithm, the researchers found that the computer consistently outperformed humans at a variation of the task in which users are shown two photos and asked which scene is closer to a McDonald's.
To create the algorithm, the team — which included PhD students Aditya Khosla, Byoungkwon An, and Joseph Lim, as well as CSAIL principal investigator Antonio Torralba — trained the computer on a set of 8 million Google images from eight major U.S. cities that were embedded with GPS data on crime rates and McDonald's locations. They then used deep-learning techniques to help the program teach itself how different qualities of the photos correlate. For example, the algorithm independently discovered that some things you often find near McDonald's franchises include taxis, police vans, and prisons. (Things you don’t find: cliffs, suspension bridges, and sandbars.)
“These sorts of algorithms have been applied to all sorts of content, like inferring the memorability of faces from headshots,” said Khosla. “But before this, there hadn’t really been research that’s taken such a large set of photos and used it to predict qualities of the specific locations the photos represent.”
The researchers presented a paper about the work at the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR) this summer.
While the project was mostly intended as proof that computer algorithms are capable of advanced scene understanding, Khosla has brainstormed potential uses ranging from a navigation app that avoids high-crime areas, to a tool that could help McDonald's determine future franchise locations.
Khosla previously helped develop an algorithm that can predict a photo’s popularity.
New frontier in error-correcting codes
New frontier in error-correcting codes
Coding scheme for interactive communication is the first to near optimality on three classical measures.
Error-correcting codes are one of the glories of the information age: They’re what guarantee the flawless transmission of digital information over the airwaves or through copper wire, even in the presence of the corrupting influences that engineers call “noise.”
But classical error-correcting codes work best with large chunks of data: The bigger the chunk, the higher the rate at which it can be transmitted error-free. In the Internet age, however, distributed computing is becoming more and more common, with devices repeatedly exchanging small chunks of data over long periods of time.
So for the last 20 years, researchers have been investigating interactive-coding schemes, which address the problem of long sequences of short exchanges. Like classical error-correcting codes, interactive codes are evaluated according to three criteria: How much noise can they tolerate? What’s the maximum transmission rate they afford? And how time-consuming are the encoding and decoding processes?
At the IEEE Symposium on Foundations of Computer Science this month, MIT graduate students past and present will describe the first interactive coding scheme to approach the optimum on all three measures.
“Previous to this work, it was known how to get two out of three of these things to be optimal,” says Mohsen Ghaffari, a graduate student in electrical engineering and computer science and one of the paper’s two co-authors. “This paper achieves all three of them.”
Vicious noise
Moreover, where Claude Shannon’s groundbreaking 1948 analysis of error-correcting codes considered the case of random noise, in which every bit of transmitted data has the same chance of being corrupted, Ghaffari and his collaborator — Bernhard Haeupler, who did his graduate work at MIT and is now an assistant professor at Carnegie Mellon University — consider the more stringent case of “adversarial noise,” in which an antagonist is trying to interfere with transmission in the most disruptive way possible.
“We don’t know what type of random noise will be the one that actually captures reality,” Ghaffari explains. “If we knew the best one, we would just use that. But generally, we don’t know. So you try to generate a coding that is as general as possible.” A coding scheme that could thwart an active adversary would also thwart any type of random noise.
Error-correcting codes — both classical and interactive — work by adding some extra information to the message to be transmitted. They might, for instance, tack on some bits that describe arithmetic relationships between the message bits. Both the message bits and the extra bits are liable to corruption, so decoding a message — extracting the true sequence of message bits from the sequence that arrives at the receiver — is usually a process of iterating back and forth between the message bits and the extra bits, trying to iron out discrepancies.
In interactive communication, the maximum tolerable error rate is one-fourth: If the adversary can corrupt more than a quarter of the bits sent, perfectly reliable communication is impossible. Some prior interactive-coding schemes, Ghaffari explains, could handle that error rate without requiring too many extra bits. But the decoding process was prohibitively complex.
Making a list
To keep the complexity down, Ghaffari and Haeupler adopted a technique called list decoding. Rather than iterating back and forth between message bits and extra bits until the single most probable interpretation emerges, their algorithm iterates just long enough to create a list of likely candidates. At the end of their mutual computation, each of the interacting devices may have a list with hundreds of entries.
But each device, while it has only imperfect knowledge of the messages sent by the other, has perfect knowledge of the messages it sent. So if, at the computation’s end, the devices simply exchange lists, each has enough additional information to zero in on the optimal decoding.
The maximum tolerable error rate for an interactive-coding scheme — one-fourth — is a theoretical result. The minimum length of an encoded message and the minimum decoding complexity, on the other hand, are surmises based on observation.
But Ghaffari and Haeupler’s decoding algorithm is nearly linear, meaning that its execution time is roughly proportional to the length of the messages exchanged.
“It is optimal in the sense that it is linear,” says Mark Braverman, an assistant professor of computer science at Princeton University who has also worked on interactive coding. “That’s an important benchmark.”
But linear relationships are still defined by constants: y = x is a linear relationship, but so is y = 1,000,000,000x. A linear algorithm that takes an extra second of computation for each additional bit of data it considers isn’t as good as a linear algorithm that takes an extra microsecond.
“We still need to worry a little bit about constants,” Braverman says. “But before you can worry about constants, you have to know that there is a constant-rate scheme. This is very nice progress and a prerequisite to asking those next questions.”
But classical error-correcting codes work best with large chunks of data: The bigger the chunk, the higher the rate at which it can be transmitted error-free. In the Internet age, however, distributed computing is becoming more and more common, with devices repeatedly exchanging small chunks of data over long periods of time.
So for the last 20 years, researchers have been investigating interactive-coding schemes, which address the problem of long sequences of short exchanges. Like classical error-correcting codes, interactive codes are evaluated according to three criteria: How much noise can they tolerate? What’s the maximum transmission rate they afford? And how time-consuming are the encoding and decoding processes?
At the IEEE Symposium on Foundations of Computer Science this month, MIT graduate students past and present will describe the first interactive coding scheme to approach the optimum on all three measures.
“Previous to this work, it was known how to get two out of three of these things to be optimal,” says Mohsen Ghaffari, a graduate student in electrical engineering and computer science and one of the paper’s two co-authors. “This paper achieves all three of them.”
Vicious noise
Moreover, where Claude Shannon’s groundbreaking 1948 analysis of error-correcting codes considered the case of random noise, in which every bit of transmitted data has the same chance of being corrupted, Ghaffari and his collaborator — Bernhard Haeupler, who did his graduate work at MIT and is now an assistant professor at Carnegie Mellon University — consider the more stringent case of “adversarial noise,” in which an antagonist is trying to interfere with transmission in the most disruptive way possible.
“We don’t know what type of random noise will be the one that actually captures reality,” Ghaffari explains. “If we knew the best one, we would just use that. But generally, we don’t know. So you try to generate a coding that is as general as possible.” A coding scheme that could thwart an active adversary would also thwart any type of random noise.
Error-correcting codes — both classical and interactive — work by adding some extra information to the message to be transmitted. They might, for instance, tack on some bits that describe arithmetic relationships between the message bits. Both the message bits and the extra bits are liable to corruption, so decoding a message — extracting the true sequence of message bits from the sequence that arrives at the receiver — is usually a process of iterating back and forth between the message bits and the extra bits, trying to iron out discrepancies.
In interactive communication, the maximum tolerable error rate is one-fourth: If the adversary can corrupt more than a quarter of the bits sent, perfectly reliable communication is impossible. Some prior interactive-coding schemes, Ghaffari explains, could handle that error rate without requiring too many extra bits. But the decoding process was prohibitively complex.
Making a list
To keep the complexity down, Ghaffari and Haeupler adopted a technique called list decoding. Rather than iterating back and forth between message bits and extra bits until the single most probable interpretation emerges, their algorithm iterates just long enough to create a list of likely candidates. At the end of their mutual computation, each of the interacting devices may have a list with hundreds of entries.
But each device, while it has only imperfect knowledge of the messages sent by the other, has perfect knowledge of the messages it sent. So if, at the computation’s end, the devices simply exchange lists, each has enough additional information to zero in on the optimal decoding.
The maximum tolerable error rate for an interactive-coding scheme — one-fourth — is a theoretical result. The minimum length of an encoded message and the minimum decoding complexity, on the other hand, are surmises based on observation.
But Ghaffari and Haeupler’s decoding algorithm is nearly linear, meaning that its execution time is roughly proportional to the length of the messages exchanged.
“It is optimal in the sense that it is linear,” says Mark Braverman, an assistant professor of computer science at Princeton University who has also worked on interactive coding. “That’s an important benchmark.”
But linear relationships are still defined by constants: y = x is a linear relationship, but so is y = 1,000,000,000x. A linear algorithm that takes an extra second of computation for each additional bit of data it considers isn’t as good as a linear algorithm that takes an extra microsecond.
“We still need to worry a little bit about constants,” Braverman says. “But before you can worry about constants, you have to know that there is a constant-rate scheme. This is very nice progress and a prerequisite to asking those next questions.”
MIT computer scientists can predict the price of Bitcoin
MIT computer scientists can predict the price of Bitcoin
CSAIL/LIDS team's algorithm doubles initial investment in under two months.
Scientists have crunched data to predict crime, hospital visits, and government uprisings — so why not the price of Bitcoin?
A researcher at MIT’s Computer Science and Artificial Intelligence Laboratory and the Laboratory for Information and Decision Systems recently developed a machine-learning algorithm that can predict the price of the infamously volatile cryptocurrency Bitcoin, allowing his team to nearly double its investment over a period of 50 days.
Earlier this year, principal investigator Devavrat Shah and recent graduate Kang Zhang collected price data from all major Bitcoin exchanges, every second for five months, accumulating more than 200 million data points.
Using a technique called “Bayesian regression,” they trained an algorithm to automatically identify patterns from the data, which they used to predict prices, and trade accordingly.
Specifically, every two seconds they predicted the average price movement over the following 10 seconds. If the price movement was higher than a certain threshold, they bought a Bitcoin; if it was lower than the opposite threshold, they sold one; and if it was in-between, they did nothing.
Over 50 days, the team’s 2,872 trades gave them an 89 percent return on investment with a Sharpe ratio (measure of return relative to the amount of risk) of 4.1.
The team’s paper was published this month at the 2014 Allerton Conference on Communication, Control, and Computing.
“We developed this method of latent-source modeling, which hinges on the notion that things only happen in a few different ways,” says Shah, who previously used the approach to predict Twitter trending topics. “Instead of making subjective assumptions about the shape of patterns, we simply take the historical data and plug it into our predictive model to see what emerges.”
Shah says he was drawn to Bitcoin because of its vast swath of free data, as well as its sizable user base of high-frequency traders.
“We needed publicly available data, in large quantities and at an extremely fine scale,” says Shah, the Jamieson Career Development Associate Professor of Electrical Engineering and Computer Science. “We were also intrigued by the challenge of predicting a currency that has seen its prices see-saw regularly in the last few years.”
In the future, Shah says he is interested in expanding the scale of the data collection to further hone the effectiveness of his algorithm.
“Can we explain the price variation in terms of factors related to the human world? We have not spent a lot of time doing that,” Shah says, before adding with a laugh, “But I can show you it works. Give me your money and I’d be happy to invest it for you.”
When Shah published his Twitter study in 2012, some academics wondered whether his approach could work for stock prices. With the Bitcoin research complete, he says he now feels confident modeling virtually any quantity that varies over time — including, he says half-jokingly, the validity of astrology predictions.
If nothing else, the findings demonstrate Shah’s belief that, more often than not, what gets in the way of our predictive powers are our preconceived notions of what patterns will pop up.
“When you get down to it,” he says, “you really should be letting the data decide.”
A researcher at MIT’s Computer Science and Artificial Intelligence Laboratory and the Laboratory for Information and Decision Systems recently developed a machine-learning algorithm that can predict the price of the infamously volatile cryptocurrency Bitcoin, allowing his team to nearly double its investment over a period of 50 days.
Earlier this year, principal investigator Devavrat Shah and recent graduate Kang Zhang collected price data from all major Bitcoin exchanges, every second for five months, accumulating more than 200 million data points.
Using a technique called “Bayesian regression,” they trained an algorithm to automatically identify patterns from the data, which they used to predict prices, and trade accordingly.
Specifically, every two seconds they predicted the average price movement over the following 10 seconds. If the price movement was higher than a certain threshold, they bought a Bitcoin; if it was lower than the opposite threshold, they sold one; and if it was in-between, they did nothing.
Over 50 days, the team’s 2,872 trades gave them an 89 percent return on investment with a Sharpe ratio (measure of return relative to the amount of risk) of 4.1.
The team’s paper was published this month at the 2014 Allerton Conference on Communication, Control, and Computing.
“We developed this method of latent-source modeling, which hinges on the notion that things only happen in a few different ways,” says Shah, who previously used the approach to predict Twitter trending topics. “Instead of making subjective assumptions about the shape of patterns, we simply take the historical data and plug it into our predictive model to see what emerges.”
Shah says he was drawn to Bitcoin because of its vast swath of free data, as well as its sizable user base of high-frequency traders.
“We needed publicly available data, in large quantities and at an extremely fine scale,” says Shah, the Jamieson Career Development Associate Professor of Electrical Engineering and Computer Science. “We were also intrigued by the challenge of predicting a currency that has seen its prices see-saw regularly in the last few years.”
In the future, Shah says he is interested in expanding the scale of the data collection to further hone the effectiveness of his algorithm.
“Can we explain the price variation in terms of factors related to the human world? We have not spent a lot of time doing that,” Shah says, before adding with a laugh, “But I can show you it works. Give me your money and I’d be happy to invest it for you.”
When Shah published his Twitter study in 2012, some academics wondered whether his approach could work for stock prices. With the Bitcoin research complete, he says he now feels confident modeling virtually any quantity that varies over time — including, he says half-jokingly, the validity of astrology predictions.
If nothing else, the findings demonstrate Shah’s belief that, more often than not, what gets in the way of our predictive powers are our preconceived notions of what patterns will pop up.
“When you get down to it,” he says, “you really should be letting the data decide.”
Keeping hydrogen from cracking metals
Keeping hydrogen from cracking metals
MIT postdoctoral associate Mostafa Youssef and graduate student Aravind Krishnamoorthy tackle different aspects of the problem at atomic scale.
Metal alloys such as steel and zirconium that are used in pipes for nuclear reactors and oil fields naturally acquire a protective oxide or sulfide layer. But hydrogen penetration can lead to their breakdown and speed up corrosion. Understanding how defects in the protective layer allow hydrogen to penetrate could lead to designing stronger, more corrosion resistant alloys.
MIT postdoctoral associate Mostafa Youssef and graduate student Aravind Krishnamoorthy are studying protective layers of iron sulfide in steel and zirconium oxide in zirconium alloys by modeling atomic level interactions. They are members of the Lab for Electrochemical Interfaces, which is directed by MIT associate professor of nuclear science and engineering Bilge Yildiz.
"We are trying to first understand fundamentally this oxide layer that grows on the metal in general; it doesn't really matter which particular metal it is," Youssef says. "Then we can engineer through alloying by inserting a percentage of other metals, in order to improve the resistance toward the degradation phenomenon that we care about, whether it's hydrogen or just the continuous corrosion. We just need a little bit of corrosion to sufficiently produce a coherent oxide layer."
"The next level after the understanding would be engineering by suggesting alloying elements on a physics-based understanding rather than empirical experimentation," he adds. "What we are trying to show is that we can understand the physical mechanism by which the process takes place and then scientifically suggest a metal based on this new knowledge."
Lattice vacancies trap hydrogen
Youssef studied how point defects in zirconium oxide can move through the material from the environment side to the underlying metal. Zirconium oxide is the native protective layer that forms on zirconium alloys used in nuclear reactors, in particular for enclosing the nuclear fuel. "If this process goes very fast, then the corrosion reaction will proceed in a fast fashion as well, and continuously will eat the whole metal. We want corrosion to take place, but we don't want it to be very fast over long time scales. We want it to just provide a sufficient protective layer, and then stop," Youssef said.
"Hydrogen is dangerous because if it gets inside the metal, it degrades its mechanical properties completely, a phenomenon called hydrogen embrittlement, and leads to premature cracking, something clearly unwanted in a nuclear reactor," Youssef explains.
Youssef and Yildiz reported on hydrogen defects in zirconium oxide, under both oxygen rich/zirconium poor and oxygen poor/zirconium rich conditions, in the Physical Chemistry Chemical Physics article, "Hydrogen defects in tetragonal ZrO2 studied using density functional theory," in November 2013. Using Density Functional Theory calculations, they modeled both single and paired hydrogen atoms at different sites in the zirconium oxide crystal lattice and also modeled their charge states. Significantly, the research showed that both oxygen vacancies and zirconium vacancies could attract hydrogen under different conditions. The simulation found that "zirconium vacancies can act as trapping sites for hydrogen and the resulting complexes can be detrimental precursors for the mechanical failure of the oxide."
The work also included signatures of hydrogen in zirconia that could be experimentally validated, such as the net spin and the vibrational frequencies of the defects. Youssef is pursuing this theme by evaluating various compositions of zirconium alloys for their effectiveness at preventing hydrogen uptake through the zirconium oxide layer, which is a cause of premature fracture.
Modeling on atomic scale
While he also uses computational analysis, fifth-year materials science and engineering doctoral student Krishnamoorthy focuses on iron sulfide films inside pipes for offshore oil fields. He is studying how hydrogen gets into the native protective layer of iron sulfide, how mechanical damage propagates through the film, and whether there are ways to make it more stable. Lab member F. William Herbert, also a graduate student in materials science and engineering, handles the experimental side, studying formation and stability of iron sulfide on iron samples.
"One of the main strengths of our group is combining both the experimental data at the lab and the computational data that we provide to get a holistic picture of what's going on from the atomic scale," Krishnamoorthy says.
Krishnamoorthy worked with Herbert, Yildiz, and associate professor of materials science and engineering Krystyn J. Van Vliet on a paper that quantified the electronic band gap and surface states of iron sulfide, also known as pyrite, establishing significant differences between its surface properties and those of the bulk material. Krishnamoorthy contributed electronic structure calculations to the work, showing that the energy bandgap at the surface of iron sulfide is less than the comparable value for the bulk material. "This finding is important in establishing accurate models for predicting corrosion rates, and also for potential solar cell or semiconductor uses for the same material," Krishnamoorthy says.
On hydrogen-related research, "You have hydrogen that gets into the film, and it makes it mechanically weak, and then the film breaks off and the surface is no longer protected," Krishnamoorthy explains. "What you want to identify is what are the physical phenomena that are responsible for hydrogen entering the film and making it mechanically weak. We're trying to model them at the atomic scale, because that is the length scale at which the required reactions happen." He identified how atomic defects inside the iron sulfide films catalyze the hydrogen reactions and lead to mechanical fracture of the films. His recent work on this finding is in review prior to publication.
A challenge in this computational work is the scaling up from tiny atomic-level simulations that model very short timeframes to large, real-world models, in which corrosion happens over months or years. Youssef says, "If you think about zirconium alloys in a nuclear reactor, the industry has to produce structures that are several meters long, and for oil and gas field applications the structures could be kilometers of these alloys. What we are trying to do is just infer the fundamental physics underlying corrosion on a nanometer scale, and we are trying to transfer this understanding, which we obtained on the nanometer scale, to the engineering level, which takes place on the miles scale." Currently, Krishnamoorty is working on addressing this problem also by developing new models which bridge his atomistic simulations to large scales for corrosion prediction.
For atomistic simulations, they use commercially-available software for quantum-mechanical calculations. For example, Youssef used Vienna Ab-initio Simulation Package (VASP) software for his work on hydrogen defects in zirconium oxide. But they also write some of their own computer code for unique aspects of the passive films and crystal structures they study. Their investigations require a multi-disciplinary approach pulling in solid state physics, statistical mechanics, electrochemistry and materials science.
Krishnamoorthy received his bachelor's degree in metallurgical and materials engineering at the Indian Institute of Technology (IIT) in Madras, India. Youssef completed his master's and PhD at MIT in nuclear science and engineering. He received his bachelor's degree in nuclear engineering at Alexandria University in Egypt.
MIT postdoctoral associate Mostafa Youssef and graduate student Aravind Krishnamoorthy are studying protective layers of iron sulfide in steel and zirconium oxide in zirconium alloys by modeling atomic level interactions. They are members of the Lab for Electrochemical Interfaces, which is directed by MIT associate professor of nuclear science and engineering Bilge Yildiz.
"We are trying to first understand fundamentally this oxide layer that grows on the metal in general; it doesn't really matter which particular metal it is," Youssef says. "Then we can engineer through alloying by inserting a percentage of other metals, in order to improve the resistance toward the degradation phenomenon that we care about, whether it's hydrogen or just the continuous corrosion. We just need a little bit of corrosion to sufficiently produce a coherent oxide layer."
"The next level after the understanding would be engineering by suggesting alloying elements on a physics-based understanding rather than empirical experimentation," he adds. "What we are trying to show is that we can understand the physical mechanism by which the process takes place and then scientifically suggest a metal based on this new knowledge."
Lattice vacancies trap hydrogen
Youssef studied how point defects in zirconium oxide can move through the material from the environment side to the underlying metal. Zirconium oxide is the native protective layer that forms on zirconium alloys used in nuclear reactors, in particular for enclosing the nuclear fuel. "If this process goes very fast, then the corrosion reaction will proceed in a fast fashion as well, and continuously will eat the whole metal. We want corrosion to take place, but we don't want it to be very fast over long time scales. We want it to just provide a sufficient protective layer, and then stop," Youssef said.
"Hydrogen is dangerous because if it gets inside the metal, it degrades its mechanical properties completely, a phenomenon called hydrogen embrittlement, and leads to premature cracking, something clearly unwanted in a nuclear reactor," Youssef explains.
Youssef and Yildiz reported on hydrogen defects in zirconium oxide, under both oxygen rich/zirconium poor and oxygen poor/zirconium rich conditions, in the Physical Chemistry Chemical Physics article, "Hydrogen defects in tetragonal ZrO2 studied using density functional theory," in November 2013. Using Density Functional Theory calculations, they modeled both single and paired hydrogen atoms at different sites in the zirconium oxide crystal lattice and also modeled their charge states. Significantly, the research showed that both oxygen vacancies and zirconium vacancies could attract hydrogen under different conditions. The simulation found that "zirconium vacancies can act as trapping sites for hydrogen and the resulting complexes can be detrimental precursors for the mechanical failure of the oxide."
The work also included signatures of hydrogen in zirconia that could be experimentally validated, such as the net spin and the vibrational frequencies of the defects. Youssef is pursuing this theme by evaluating various compositions of zirconium alloys for their effectiveness at preventing hydrogen uptake through the zirconium oxide layer, which is a cause of premature fracture.
Modeling on atomic scale
While he also uses computational analysis, fifth-year materials science and engineering doctoral student Krishnamoorthy focuses on iron sulfide films inside pipes for offshore oil fields. He is studying how hydrogen gets into the native protective layer of iron sulfide, how mechanical damage propagates through the film, and whether there are ways to make it more stable. Lab member F. William Herbert, also a graduate student in materials science and engineering, handles the experimental side, studying formation and stability of iron sulfide on iron samples.
"One of the main strengths of our group is combining both the experimental data at the lab and the computational data that we provide to get a holistic picture of what's going on from the atomic scale," Krishnamoorthy says.
Krishnamoorthy worked with Herbert, Yildiz, and associate professor of materials science and engineering Krystyn J. Van Vliet on a paper that quantified the electronic band gap and surface states of iron sulfide, also known as pyrite, establishing significant differences between its surface properties and those of the bulk material. Krishnamoorthy contributed electronic structure calculations to the work, showing that the energy bandgap at the surface of iron sulfide is less than the comparable value for the bulk material. "This finding is important in establishing accurate models for predicting corrosion rates, and also for potential solar cell or semiconductor uses for the same material," Krishnamoorthy says.
On hydrogen-related research, "You have hydrogen that gets into the film, and it makes it mechanically weak, and then the film breaks off and the surface is no longer protected," Krishnamoorthy explains. "What you want to identify is what are the physical phenomena that are responsible for hydrogen entering the film and making it mechanically weak. We're trying to model them at the atomic scale, because that is the length scale at which the required reactions happen." He identified how atomic defects inside the iron sulfide films catalyze the hydrogen reactions and lead to mechanical fracture of the films. His recent work on this finding is in review prior to publication.
A challenge in this computational work is the scaling up from tiny atomic-level simulations that model very short timeframes to large, real-world models, in which corrosion happens over months or years. Youssef says, "If you think about zirconium alloys in a nuclear reactor, the industry has to produce structures that are several meters long, and for oil and gas field applications the structures could be kilometers of these alloys. What we are trying to do is just infer the fundamental physics underlying corrosion on a nanometer scale, and we are trying to transfer this understanding, which we obtained on the nanometer scale, to the engineering level, which takes place on the miles scale." Currently, Krishnamoorty is working on addressing this problem also by developing new models which bridge his atomistic simulations to large scales for corrosion prediction.
For atomistic simulations, they use commercially-available software for quantum-mechanical calculations. For example, Youssef used Vienna Ab-initio Simulation Package (VASP) software for his work on hydrogen defects in zirconium oxide. But they also write some of their own computer code for unique aspects of the passive films and crystal structures they study. Their investigations require a multi-disciplinary approach pulling in solid state physics, statistical mechanics, electrochemistry and materials science.
Krishnamoorthy received his bachelor's degree in metallurgical and materials engineering at the Indian Institute of Technology (IIT) in Madras, India. Youssef completed his master's and PhD at MIT in nuclear science and engineering. He received his bachelor's degree in nuclear engineering at Alexandria University in Egypt.
วันพุธที่ 5 พฤศจิกายน พ.ศ. 2557
Parallel programming may not be so daunting
Parallel programming may not be so daunting
“Lock-free” parallel algorithms may match performance of more complex “wait-free” algorithms.
Computer chips have stopped getting faster: The regular performance improvements we’ve come to expect are now the result of chipmakers’ adding more cores, or processing units, to their chips, rather than increasing their clock speed.
In theory, doubling the number of cores doubles the chip’s efficiency, but splitting up computations so that they run efficiently in parallel isn’t easy. On the other hand, say a trio of computer scientists from MIT, Israel’s Technion, and Microsoft Research, neither is it as hard as had been feared.
Commercial software developers writing programs for multicore chips frequently use so-called “lock-free” parallel algorithms, which are relatively easy to generate from standard sequential code. In fact, in many cases the conversion can be done automatically.
Yet lock-free algorithms don’t come with very satisfying theoretical guarantees: All they promise is that at least one core will make progress on its computational task in a fixed span of time. But if they don’t exceed that standard, they squander all the additional computational power that multiple cores provide.
In recent years, theoretical computer scientists have demonstrated ingenious alternatives called “wait-free” algorithms, which guarantee that all cores will make progress in a fixed span of time. But deriving them from sequential code is extremely complicated, and commercial developers have largely neglected them.
In a paper to be presented at the Association for Computing Machinery’s Annual Symposium on the Theory of Computing in May, Nir Shavit, a professor in MIT’s Department of Electrical Engineering and Computer Science; his former student Dan Alistarh, who’s now at Microsoft Research; and Keren Censor-Hillel of the Technion demonstrate a new analytic technique suggesting that, in a wide range of real-world cases, lock-free algorithms actually give wait-free performance.
“In practice, programmers program as if everything is wait-free,” Shavit says. “This is a kind of mystery. What we are exposing in the paper is this little-talked-about intuition that programmers have about how [chip] schedulers work, that they are actually benevolent.”
The researchers’ key insight was that the chip’s performance as a whole could be characterized more simply than the performance of the individual cores. That’s because the allocation of different “threads,” or chunks of code executed in parallel, is symmetric. “It doesn’t matter whether thread 1 is in state A and thread 2 is in state B or if you just swap the states around,” says Alistarh, who contributed to the work while at MIT. “What we noticed is that by coalescing symmetric states, you can simplify this a lot.”
In a real chip, the allocation of threads to cores is “a complex interplay of latencies and scheduling policies,” Alistarh says. In practice, however, the decisions arrived at through that complex interplay end up looking a lot like randomness. So the researchers modeled the scheduling of threads as a process that has at least a little randomness in it: At any time, there’s some probability that a new thread will be initiated on any given core.
The researchers found that even with a random scheduler, a wide range of lock-free algorithms offered performance guarantees that were as good as those offered by wait-free algorithms.
That analysis held, no matter how the probability of thread assignment varied from core to core. But the researchers also performed a more specific analysis, asking what would happen when multiple cores were trying to write data to the same location in memory and one of them kept getting there ahead of the others. That’s the situation that results in a lock-free algorithm’s worst performance, when only one core is making progress.
For that case, they considered a particular set of probabilities, in which every core had the same chance of being assigned a thread at any given time. “This is kind of a worst-case random scheduler,” Alistarh says. Even then, however, the number of cores that made progress never dipped below the square root of the number of cores assigned threads, which is still better than the minimum performance guarantee of lock-free algorithms.
In theory, doubling the number of cores doubles the chip’s efficiency, but splitting up computations so that they run efficiently in parallel isn’t easy. On the other hand, say a trio of computer scientists from MIT, Israel’s Technion, and Microsoft Research, neither is it as hard as had been feared.
Commercial software developers writing programs for multicore chips frequently use so-called “lock-free” parallel algorithms, which are relatively easy to generate from standard sequential code. In fact, in many cases the conversion can be done automatically.
Yet lock-free algorithms don’t come with very satisfying theoretical guarantees: All they promise is that at least one core will make progress on its computational task in a fixed span of time. But if they don’t exceed that standard, they squander all the additional computational power that multiple cores provide.
In recent years, theoretical computer scientists have demonstrated ingenious alternatives called “wait-free” algorithms, which guarantee that all cores will make progress in a fixed span of time. But deriving them from sequential code is extremely complicated, and commercial developers have largely neglected them.
In a paper to be presented at the Association for Computing Machinery’s Annual Symposium on the Theory of Computing in May, Nir Shavit, a professor in MIT’s Department of Electrical Engineering and Computer Science; his former student Dan Alistarh, who’s now at Microsoft Research; and Keren Censor-Hillel of the Technion demonstrate a new analytic technique suggesting that, in a wide range of real-world cases, lock-free algorithms actually give wait-free performance.
“In practice, programmers program as if everything is wait-free,” Shavit says. “This is a kind of mystery. What we are exposing in the paper is this little-talked-about intuition that programmers have about how [chip] schedulers work, that they are actually benevolent.”
The researchers’ key insight was that the chip’s performance as a whole could be characterized more simply than the performance of the individual cores. That’s because the allocation of different “threads,” or chunks of code executed in parallel, is symmetric. “It doesn’t matter whether thread 1 is in state A and thread 2 is in state B or if you just swap the states around,” says Alistarh, who contributed to the work while at MIT. “What we noticed is that by coalescing symmetric states, you can simplify this a lot.”
In a real chip, the allocation of threads to cores is “a complex interplay of latencies and scheduling policies,” Alistarh says. In practice, however, the decisions arrived at through that complex interplay end up looking a lot like randomness. So the researchers modeled the scheduling of threads as a process that has at least a little randomness in it: At any time, there’s some probability that a new thread will be initiated on any given core.
The researchers found that even with a random scheduler, a wide range of lock-free algorithms offered performance guarantees that were as good as those offered by wait-free algorithms.
That analysis held, no matter how the probability of thread assignment varied from core to core. But the researchers also performed a more specific analysis, asking what would happen when multiple cores were trying to write data to the same location in memory and one of them kept getting there ahead of the others. That’s the situation that results in a lock-free algorithm’s worst performance, when only one core is making progress.
For that case, they considered a particular set of probabilities, in which every core had the same chance of being assigned a thread at any given time. “This is kind of a worst-case random scheduler,” Alistarh says. Even then, however, the number of cores that made progress never dipped below the square root of the number of cores assigned threads, which is still better than the minimum performance guarantee of lock-free algorithms.
สมัครสมาชิก:
บทความ (Atom)
Custom Search