Compressing rectilinear pictures and minimizing access control lists

US7958075B1 · kind B1 · utility

Assignee

• AT&T Intellectual Property I, L.P. · US

Inventors

• David Lee Applegate · Maplewood, US
• Gruia Calinescu · Wilmette, US
• David Scott Johnson · Portola Valley, US
• Howard Karloff · New York, US
• Katrina Ligett · Pittsburgh, US
• Jia-Li Wang · Dover, US

Key dates

• Filing date: Jun 28, 2007
• Grant date: Jun 7, 2011
• Expiry date: Apr 6, 2030

Classification

• Technology area (CPC G): Physics
• CPC primary: G06T9/00
• WIPO field: Computer technology
• WIPO sector: Electrical engineering

Abstract

A geometric model is considered for the problem of minimizing access control lists (ACLs) in network routers. A colored rectilinear pattern is created within an initially white rectangular canvas, and the basic operation is to choose a subrectangle and paint it a single color, overwriting all previous colors in the rectangle. The method operates on rectangular rule lists (RRLs) and access control lists (ACLs) in which all rectangles are strips that extend either the full length or the full height of the canvas. A polynomial-time algorithm optimally constructs such patterns when, as in the ACL application, the only colors are black and white (permit or deny). That algorithm is complemented by a significantly faster approximation algorithm that is guaranteed to be no worse than 3/2 optimal.